import java.util.Arrays;

/*
 * @lc app=leetcode.cn id=785 lang=java
 *
 * [785] 判断二分图
 */

// @lc code=start
class Solution {
    int red = 0;
    int green = 1;
    int[] color;
    boolean valid = true;

    public boolean isBipartite(int[][] graph) {
        color = new int[graph.length];
        Arrays.fill(color, -1);
        for (int i = 0; i < graph.length && valid; i++) {
            if (color[i] == -1) {
                dfs(i, red, graph);
            }
        }
        return valid;
    }

    public void dfs(int i, int c, int[][] graph) {
        color[i] = c;
        int newColor = c == red ? green : red;
        for (int neighbor : graph[i]) {
            if (color[neighbor] == -1) {
                dfs(neighbor, newColor, graph);
                if (!valid) {
                    return;
                }
            } else if (color[neighbor] != newColor) {
                valid = false;
                return;
            }

        }
    }
}
// @lc code=end
